/*
 * Question: Try to propose a recursive algorithm calculates
 * the value of the node which is at the kth position in the
 * prefix order sequence of a binary tree.
 */

#include <iostream>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>
{
};

/*
 * The position in prefix order sequence is
 * counted by variable parameter k.
 */
bitree *kth_value(bitree *rt, int &k)
{
    bitree *r;

    if (!rt)
        return NULL;
    if (--k == 0)
        return rt;
    r = kth_value(rt->lchild, k);
    if (r)
        return r;
    r = kth_value(rt->rchild, k);
    if (r)
        return r;
    return NULL;
}

/*
 * This is a more logic clear but less efficient
 * solution to the problem.
 *      (1) If 'rt' is empty tree, return NULL;
 *      (2) If 'rt' is the target, return it.
 *      (3) Travel the left subtree of 'rt'. If the
 *          the target is found in left subtree,
 *          return it.
 *      (4) Otherwise, try to find the target in the
 *          right subtree of 'rt'. The target is at the
 *          (k-1-lnum)th (lnum is the left subtree's node
 *          number) position of the prefix order sequence
 *          of the right subtree.
 *      (5) If there is no the target in the left and right
 *          subtree, return NULL.
 */
bitree *kth_value1(bitree *rt, int k, int &num)
{
    bitree *r;
    int lnum = 0, rnum = 0;

    if (!rt)
        return NULL;
    if (k == 1)
        return rt;
    r = kth_value1(rt->lchild, k-1, lnum);
    if (r)
        return r;
    r = kth_value1(rt->rchild, k-1-lnum, rnum);
    if (r)
        return r;
    num = lnum + rnum +1;
    return NULL;
}

int main()
{
    bitree *rt, *r;
    int k = 9, num;

    bitree_create<bitree, char>(rt, "ex41.txt");
    bitree_print(rt);
    r = kth_value1(rt, k, num);
    if (!r)
        cout << "Not found." << endl;
    else
        cout << r->key << endl;
    bitree_destory(rt);

    return 0;
}
